package LeetCode.exercise;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class LC40 {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    boolean[] flag;
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        flag = new boolean[candidates.length];
        Arrays.sort(candidates);
        bfs(candidates, target, 0, 0);
        return res;
    }
    public void bfs(int[] nums, int target, int pos, int sum){
        if(sum == target){
            res.add(new ArrayList<>(path));
            return;
        }
        if(sum > target || pos == nums.length){
            return;
        }
        for(int i = pos; i < nums.length; i++){
            if(!flag[i] && (i == 0 || nums[i] != nums[i-1] || flag[i-1])){
                path.add(nums[i]);
                flag[i] = true;
                bfs(nums, target, i+1, sum + nums[i]);
                path.remove(path.size()-1);
                flag[i] = false;
            }
        }
    }
}
